package leetcode.divide_and_conquer;

/**
 * @author mazouri
 * @create 2021-12-27 19:08
 */
public class _23_mergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int begin, int end) {
        if (begin == end) return lists[begin];

        int mid = begin + (end - begin) / 2;
        System.out.println(begin+"  "+mid+"    "+(mid+1)+"  "+end);
        ListNode l1 = merge(lists, begin, mid);
        ListNode l2 = merge(lists, mid + 1, end);
        return mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, head1 = a, head2 = b;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        tail.next = (head1 != null ? head1 : head2);
        return head.next;
    }
}
